package elementaryAlgorithm;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * @author 郭辉
 * @className TODO
 * @description
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 *
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母组成
 * 通过次数1,115,332提交次数3,023,454
 * @date 2022/7/20 19:37
 * @company 海康威视
 * @since 1.0.0
 */
public class LongestPalindromicSubstring {
    public boolean isPalindromicSubstring(List<Character> pam){
        int l = pam.size();
        for (int i = 0; i < pam.size(); i++) {
            if (pam.get(i) != pam.get(l-1-i)){
                return false;
            }
        }
        return true;
    }

    public String longestPalindrome(String s) {
        if (s.length() == 0 || s.length() == 1){
            return s;
        }
        char[] chars = s.toCharArray();
        List<List<Character>> maps = new ArrayList<>();
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            list.add(chars[i]);
            for (int j = i+1; j < chars.length; j++) {
                list.add(chars[j]);
                if (isPalindromicSubstring(list)){
                    List<Character> objects = new ArrayList<>();
                    objects.addAll(list);
                    maps.add(objects);
                }
            }
            list.clear();
        }
        int max = 0;
        int index = 0;
        for (int i = 0; i < maps.size(); i++) {
            if (maps.get(i).size() > max ){
                max = maps.get(i).size();
                index = i;
            }
        }
        String result = "";
        if (!Objects.isNull(maps) && maps.size()!=0){
            for (int i = 0; i < maps.get(index).size(); i++) {
                result+=maps.get(index).get(i);
            }
        } else if (maps.size()==0 && s.length()>0){
            return String.valueOf(chars[0]);
        }
        return result;
    }

    /**
     * @description: 正确答案（题解）
     * @author: guohui13
     * @date: 2022/7/27 19:54
     * @param: s
     * @return: java.lang.String
     **/
    public String rightAnswer(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }

                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    /**
     * @description: 尝试模仿题解
     * @author: guohui13
     * @date: 2022/7/27 20:00
     * @param: s
     * @return: java.lang.String
     **/
    public String tryRightAnswer(String s) {
        int len = s.length();
        if (len<=1){
            return s;
        }
        char[] chars = s.toCharArray();
        // dp数据定义
        boolean [][] dp = new boolean[len][len];
        // 初始化dp
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        // 穷举
        int R = 0;
        // 一层循穷举子串长度
        for (int L = 2; L <= len; L++) {
            // 二层循环穷举左边界
            for (int i = 0; i < len; i++){
                R = L+i-1;
                //如果有边界不合法，则跳出循环
                if (R >= len){
                    break;
                }
                //状态转移
                if (chars[i] != chars[R]){
                    dp[i][R]=false;
                }else {
                    if (R-i <=2){
                        dp[i][R] = true;
                    }else {
                        dp[i][R] = dp[i+1][R-1];
                    }
                }
            }
        }
        //遍历找出最大长度
        int begin = 0,end =0,maxLen = 0;
        for (int i = 0; i<len;i++){
            for (int j = 0; j < len; j++) {
                if (dp[i][j]){
                    if (j-i +1 > maxLen){
                        maxLen = j-i+1;
                        begin = i;
                        end = j;
                    }
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }



    public static void main(String[] args) {
        String pam = "";
        LongestPalindromicSubstring longestPalindromicSubstring = new LongestPalindromicSubstring();
        String palindromicSubstring = longestPalindromicSubstring.tryRightAnswer(pam);
        System.out.println(palindromicSubstring);
    }
}
